#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct AVLNode {
	T key;
	int bf;
	struct AVLNode* LChild, * RChild;

		AVLNode() {
		bf = 0;
		this->LChild = nullptr;
		this->RChild = nullptr;
	}
	AVLNode(T temp) : key(temp), LChild(nullptr), RChild(nullptr),bf(0){}
};

class AVLTree {
	typedef pair<string, string> word;
	typedef AVLNode<word> AVLNode, *BiTree;
	public:
		AVLTree(){}

		~AVLTree(){}

		string getKey(AVLNode *w) {
			return w->key.first;
		}

		string getValue(AVLNode *w) {
			return w->key.second;
		}
		
		int getHeight(AVLNode *w) {
			return w->bf;
		}

        BiTree NewNode(string key,string value){
            BiTree w = new AVLNode(make_pair(key,value));
            return w;
        }

		void R_Rotate(BiTree *w) {
			//建立一个临时的节点指向当前节点的左孩子
			BiTree L;
			L = (*w)->LChild;
			//将当前节点的左节点指向临时节点的右孩子
			(*w)->LChild = L->RChild;
			//让临时节点指向当前节点完成右旋
			L->RChild = (*w);
			//w指向新节点
			*w = L;
		}

		void L_Rotate(BiTree *w){
			//建立一个临时的节点指向当前节点的右孩子
			BiTree R;
			R = (*w)->RChild;
			//将当前节点的右孩子指向临时节点的左孩子
			(*w)->RChild = R->LChild;
			//让临时节点指向当前节点完成左旋
			R->LChild = (*w);
			//w指向新节点
            *w = R; 
		}

		void LeftBalance(BiTree *w) {
			BiTree L,Lr;
			L = (*w)->LChild; 
			if (L->bf == 1) {
				(*w)->bf = L->bf = 0;
				R_Rotate(w); 
			}else{
                Lr = L->RChild;
                if(Lr->bf == 1){
                    (*w)->bf = -1;
                    L->bf = 0;
                }else if(Lr->bf == 0){
                    (*w)->bf = L->bf = 0;
                }else if(Lr->bf == -1){
                    (*w)->bf = 0;
                    L->bf = 1;
                }
                Lr->bf = 0;
                L_Rotate(&(*w)->LChild);
                R_Rotate(w);
            }
		}

        void RightBalance(BiTree *w){
            BiTree R,Rl;
            R = (*w)->RChild;
            if(R->bf == -1){
                (*w)->bf = R->bf = 0;
                L_Rotate(w);
            }else{
                Rl = R->LChild;
                if(Rl->bf == -1){
                    (*w)->bf = 1;
                    R->bf = 0;
                }else if(Rl->bf == 0){
                    (*w)->bf = R->bf = 0;
                }else if(Rl->bf == 1){
                    (*w)->bf = 0;
                    R->bf = -1;
                }
                Rl->bf = 0;
                R_Rotate(&(*w)->RChild);
                L_Rotate(w);
            }
        }

        void InsertAVL(BiTree *w,string key,string value,bool *taller){
            if(!*w){
                (*w) = NewNode(key,value);
                *taller = true;
                return ;
            }else{
                if(key < getValue(*w)){
                    InsertAVL(&(*w)->LChild,key,value,taller);
                    if(*taller){
                        if((*w)->bf == 1){
                            LeftBalance(w);
                            *taller = false;
                        }else if((*w)->bf == 0){
                            (*w)->bf = 1;
                            *taller = true;
                        }else{
                            (*w)->bf = 0;
                            *taller = false;
                        }
                    }
                }else{
                    InsertAVL(&(*w)->RChild,key,value,taller);
                    if(*taller){
                        if((*w)->bf == 1){
                            (*w)->bf = 0;
                            *taller = false;
                        }else if((*w)->bf == 0){
                            (*w)->bf = -1;
                            *taller = true;
                        }else{
                            RightBalance(w);
                            *taller = false;
                        }
                    }
                }
            }
        }
};



int main(){
    
}